package com.hy.prefix_add;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:除自身以外数组的乘积
 *
 * 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
 * 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
 * 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
 * author: Mr.Du
 * Date: 2023/9/26
 * Time: 11:30
 */
public class ProductExceptSelf {

    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        // 前缀积，从前往后计算
        int[] pre = new int[n];
        pre[0] = nums[0];
        for(int i = 1; i < n; i++){
            pre[i] = pre[i - 1] * nums[i];
        }
        // 后缀积，从后往前计算
        int[] sur = new int[n];
        sur[n - 1] = nums[n-1];
        for(int i = n - 2;i >= 0;i--){
            sur[i] = sur[i + 1] * nums[i];
        }
        // 结果集
        int[] res = new int[n];
        res[n - 1] = pre[n-2];
        res[0] = sur[1];
        for(int i = 1;i < n - 1;i++){
            res[i] = pre[i - 1] * sur[i + 1];
        }
        return res;
    }
}
